SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Computational problem</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Computational problem</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, a <b> problem</b> is one that asks for a solution in terms of an <a href="Algorithm" title="Algorithm">algorithm</a>. For example, the problem of <b>factoring</b>

</p>

<dl><dd>"Given a positive integer <i>n</i>, find a nontrivial prime factor of <i>n</i>."</dd></dl>

<p>is a computational problem that has a solution, as there are many known <a href="Integer_factorization" title="Integer factorization">integer factorization</a> algorithms. A computational problem can be viewed as a <a href="Set_(mathematics)" title="Set (mathematics)">set</a> of <i>instances</i> or <i>cases</i> together with a, possibly empty, set of <i>solutions</i> for every instance/case. The question then is, whether there exists an algorithm that maps instances to solutions. For example, in the <a href="Factoring_problem" class="mw-redirect" title="Factoring problem">factoring problem</a>, the instances are the integers <i>n</i>, and solutions are prime numbers <i>p</i> that are the nontrivial prime factors of <i>n</i>. An example of a computational problem without a solution is the <a href="Halting_problem" title="Halting problem">Halting problem</a>. Computational problems are one of the main objects of study in theoretical computer science.

</p><p>One is often interested not only in mere existence of an algorithm, but also how efficient the algorithm can be. The field of <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a> addresses such questions by determining the amount of resources (<a href="Computational_complexity" title="Computational complexity">computational complexity</a>) solving a given problem will require, and explain why some problems are <a href="Computational_complexity_theory#Intractability" title="Computational complexity theory">intractable</a> or <a href="Undecidable_problem" title="Undecidable problem">undecidable</a>. Solvable computational problems belong to <a href="Complexity_class" title="Complexity class">complexity classes</a> that define broadly the resources (e.g. time, space/memory, energy, circuit depth) it takes to compute (solve) them with various <a href="Abstract_machine" title="Abstract machine">abstract machines</a>. For example, the complexity classes

</p>

<ul><li><b><a href="P_(complexity)" title="P (complexity)">P</a></b>, problems that consume polynomial time for deterministic classical machines</li>

<li><b><a href="BPP_(complexity)" title="BPP (complexity)">BPP</a></b>, problems that consume polynomial time for probabilistic classical machines (e.g. computers with random number generators)</li>

<li><b><a href="BQP" title="BQP">BQP</a></b>, problems that consume polynomial time for probabilistic quantum machines.</li></ul>

<p>Both instances and solutions are represented by binary <a href="String_(computer_science)" title="String (computer science)">strings</a>, namely elements of {0, 1}<sup>*</sup>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>a<span class="cite-bracket">]</span></a></sup> For example, <a href="Natural_numbers" class="mw-redirect" title="Natural numbers">natural numbers</a> are usually represented as binary strings using <a href="Binary_number" title="Binary number">binary encoding</a>. This is important since the complexity is expressed as a function of the length of the input representation.

</p>

<div class="mw-heading mw-heading2"><h2 id="Types">Types</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Decision_problem">Decision problem</h3></div>

<p>A <a href="Decision_problem" title="Decision problem">decision problem</a> is a computational problem where the answer for every instance is either yes or no. An example of a decision problem is <i><a href="Primality_testing" class="mw-redirect" title="Primality testing">primality testing</a></i>:

</p>

<dl><dd>"Given a positive integer <i>n</i>, determine if <i>n</i> is prime."</dd></dl>

<p>A decision problem is typically represented as the set of all instances for which the answer is <i>yes</i>. For example, primality testing can be represented as the infinite set

</p>

<div class="mw-heading mw-heading3"><h3 id="Search_problem">Search problem</h3></div>

<p>In a <a href="Search_problem" title="Search problem">search problem</a>, the answers can be arbitrary strings. For example, factoring is a search problem where the instances are (string representations of) positive integers and the solutions are (string representations of) collections of primes.

</p><p>A search problem is represented as a <a href="Relation_(mathematics)" title="Relation (mathematics)">relation</a> consisting of all the instance-solution pairs, called a <i>search relation</i>. For example, factoring can be represented as the relation

</p>

<p>which consist of all pairs of numbers (<i>n</i>, <i>p</i>), where <i>p</i> is a prime factor of <i>n</i>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Counting_problem">Counting problem</h3></div>

<p>A <a href="Counting_problem_(complexity)" title="Counting problem (complexity)">counting problem</a> asks for the number of solutions to a given search problem. For example, a counting problem associated with factoring is

</p>

<dl><dd>"Given a positive integer <i>n</i>, count the number of nontrivial prime factors of <i>n</i>."</dd></dl>

<p>A counting problem can be represented by a function <i>f</i> from {0, 1}<sup>*</sup> to the nonnegative integers. For a search relation <i>R</i>, the counting problem associated to <i>R</i> is the function

</p>

<div class="mw-heading mw-heading3"><h3 id="Optimization_problem">Optimization problem</h3></div>

<p>An <a href="Optimization_problem" title="Optimization problem">optimization problem</a> asks for finding a "best possible" solution among the set of all possible solutions to a search problem. One example is the <i>maximum independent set</i> problem:

</p>

<dl><dd>"Given a graph <i>G</i>, find an independent set of <i>G</i> of maximum size."</dd></dl>

<p>Optimization problems are represented by their objective function and their constraints.

</p>

<div class="mw-heading mw-heading3"><h3 id="Function_problem">Function problem</h3></div>

<p>In a <a href="Function_problem" title="Function problem">function problem</a> a single output (of a <a href="Total_function" class="mw-redirect" title="Total function">total function</a>) is expected for every input, but the output is more complex than that of a <a href="Decision_problem" title="Decision problem">decision problem</a>, that is, it isn't just "yes" or "no". One of the most famous examples is the <i><a href="Travelling_salesman_problem" title="Travelling salesman problem"> traveling salesman</a></i> problem:

</p>

<dl><dd>"Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city."</dd></dl>

<p>It is an <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> problem in <a href="Combinatorial_optimization" title="Combinatorial optimization">combinatorial optimization</a>, important in <a href="Operations_research" title="Operations research">operations research</a> and <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Promise_problem">Promise problem</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Promise_problem" title="Promise problem">Promise problem</a></div>

<p>In <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, it is usually implicitly assumed that any string in {0, 1}<sup>*</sup> represents an instance of the computational problem in question. However, sometimes not all strings {0, 1}<sup>*</sup> represent valid instances, and one specifies a proper subset of {0, 1}<sup>*</sup> as the set of "valid instances". Computational problems of this type are called <a href="Promise_problem" title="Promise problem">promise problems</a>.

</p><p>The following is an example of a (decision) promise problem:

</p>

<dl><dd>"Given a graph <i>G</i>, determine if every <a href="Independent_set_(graph_theory)" title="Independent set (graph theory)">independent set</a> in <i>G</i> has size at most 5, or <i>G</i> has an independent set of size at least 10."</dd></dl>

<p>Here, the valid instances are those graphs whose maximum independent set size is either at most 5 or at least 10.

</p><p>Decision promise problems are usually represented as pairs of disjoint subsets (<i>L</i><sub>yes</sub>, <i>L</i><sub>no</sub>) of {0, 1}<sup>*</sup>. The valid instances are those in <i>L</i><sub>yes</sub> ∪ <i>L</i><sub>no</sub>.

<i>L</i><sub>yes</sub> and <i>L</i><sub>no</sub> represent the instances whose answer is <i>yes</i> and <i>no</i>, respectively.

</p><p>Promise problems play an important role in several areas of <a href="Analysis_of_algorithms" title="Analysis of algorithms">computational complexity</a>, including <a href="Hardness_of_approximation" title="Hardness of approximation">hardness of approximation</a>, <a href="Property_testing" title="Property testing">property testing</a>, and <a href="Interactive_proof_system" title="Interactive proof system">interactive proof systems</a>.

</p>

<ul><li><a href="Lateral_computing" title="Lateral computing">Lateral computing</a>, alternative approaches to solving problems computationally</li>

<li><a href="Model_of_computation" title="Model of computation">Model of computation</a></li>

<li><a href="Transcomputational_problem" title="Transcomputational problem">Transcomputational problem</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-lower-alpha">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">See <a href="Regular_expression" title="Regular expression">regular expressions</a> for the notation used</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFEvenSelmanYacobi1984" class="citation cs2"><a href="Shimon_Even" title="Shimon Even">Even, Shimon</a>; <a href="Alan_Selman" title="Alan Selman">Selman, Alan L.</a>; Yacobi, Yacov (1984), "The complexity of promise problems with applications to public-key cryptography", <i>Information and Control</i>, <b>61</b> (2): <span class="nowrap">159–</span>173, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0019-9958%2884%2980056-X">10.1016/S0019-9958(84)80056-X</a></cite>.</li>

<li><cite id="CITEREFGoldreich2008" class="citation cs2"><a href="Oded_Goldreich" title="Oded Goldreich">Goldreich, Oded</a> (2008), <i>Computational Complexity: A Conceptual Perspective</i>, <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-88473-0</bdi></cite>.</li>

<li><cite id="CITEREFGoldreichWigderson2008" class="citation cs2"><a href="Oded_Goldreich" title="Oded Goldreich">Goldreich, Oded</a>; <a href="Avi_Wigderson" title="Avi Wigderson">Wigderson, Avi</a> (2008), "IV.20 Computational Complexity", in <a href="Timothy_Gowers" title="Timothy Gowers">Gowers, Timothy</a>; Barrow-Green, June; <a href="Imre_Leader" title="Imre Leader">Leader, Imre</a> (eds.), <i><a href="The_Princeton_Companion_to_Mathematics" title="The Princeton Companion to Mathematics">The Princeton Companion to Mathematics</a></i>, Princeton University Press, pp. <span class="nowrap">575–</span>604, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-691-11880-2</bdi></cite>.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-17" href="https://en.wikipedia.org/wiki/?title=Computational_problem&oldid=1300923757">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>